import java.util.Scanner;
public class prog {






//    反转链表2
//    public static String fun(String str,int begin,int end){
//        char[] arr=str.toCharArray();
//        while(begin<end){
//            char tmp=arr[begin];
//            arr[begin]=arr[end];
//            arr[end]=tmp;
//            end--;
//            begin++;
//        }
//        return String.copyValueOf(arr);
//    }
//    public static void main(String[] args) {
//        Scanner scan=new Scanner(System.in);
//        String str=scan.nextLine();
//        int len=scan.nextInt();
//        str=fun(str,0,len-1);
//        str=fun(str,len,str.length()-1);
//        str=fun(str,0,str.length()-1);
//        System.out.println(str);
//    }
}
//循环右移
//import java.util.*;
//
//
//public class Solution {
//    /**
//     * 位移后二进制串的十进制值
//     * @param str string字符串 二进制字符串
//     * @param k int整型 循环位移次数
//     * @return long长整型
//     */
//    public long rotateRight (String str, int k) {
//        // write code here
//        int len=str.length();获取字符串长度
//        String arr=str.substring(len-k)+str.substring(0,len-k);substring拼接出旋转后的字符串
//        return Long.parseLong(arr,2);此方法为转换为基本类型long的方法，
//    }
//}









//旋转字符串
//import java.util.*;
//
//
//public class Solution {
//    /**
//     * 旋转字符串
//     * @param A string字符串
//     * @param B string字符串
//     * @return bool布尔型
//     */
//    public boolean solve (String A, String B) {
//        // write code here
//        if(A.length()!=B.length()){判断两个字符串是否相等
//            return false;
//        }
//        String s=A+A;拼接字符串
//        int lena=A.length();
//        int lenb=B.length();
//        for(int i=0;i<lenb+1;i++){
//            if(s.substring(i,i+lena).equals(B)){
//            循环判断是否相同假设a=youzan   b=zanyou 中间分隔后旋转，是否与B相同，拼接后的s=youzanyouzan；
//            循环lena次一定能找到
//                return true;
//            }
//        }
//        return false;
//    }
//}










    //第一个只出现一次的字符
    //public class Solution {
    //    public int FirstNotRepeatingChar(String str) {
    //        char[] arr=str.toCharArray();
    //        boolean bool=false;
    //        for(int i=0;i<str.length();i++){
    //            bool=false;
    //            for(int j=0;j<str.length();j++){
    //                if(arr[i]==arr[j]&&i!=j){
    //                    bool=true;
    //                }
    //            }
    //            if(bool==false){
    //                return i;
    //            }
    //        }
    //        return -1;
    //    }
    //}










//最长公共前缀
//import java.util.*;
//
//
//public class Solution {
//    /**
//     *
//     * @param strs string字符串一维数组
//     * @return string字符串
//     */
//    public String longestCommonPrefix (String[] strs) {
//        // write code here
//        if(strs==null||strs.length==0){
//            return "";
//        }
//        String first=strs[0];
//        for(int i=0;i<first.length();i++){
//            for(int j=1;j<strs.length;j++){
//                if(strs[j].length()<=i){
//                    return first.substring(0,i);
//                }
//                if(strs[j].charAt(i)!=first.charAt(i)){
//                    if(i==0){
//                        return "";
//                    }
//                    return first.substring(0,i);
//                }
//            }
//        }
//        return first;
//    }
//}










//移动字母
//import java.util.*;
//
//
//public class Solution {
//    /**
//     *
//     * @param s string字符串
//     * @return string字符串
//     */
//    public String change (String s) {
//        // write code here
//        char[] arr=s.toCharArray();
//        int j=0;
//        for(int i=0;i<s.length();i++){
//            if(arr[i]!='a'){
//                arr[j++]=arr[i];
//            }
//        }
//        for(;j<s.length();j++){
//            arr[j]='a';
//        }
//        return String.copyValueOf(arr);
//    }
//}










//打字
//import java.util.*;
//
//
//public class Solution {
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     *
//     * @param s string字符串
//     * @return string字符串
//     */
//    public String Typing (String s) {
//        // write code here
//        if(s.length()==0){
//            return s;
//        }
//        char[] arr=s.toCharArray();
//        char[] str=new char[s.length()];
//        int size=0;
//        for(int i=0;i<s.length();i++){
//            if(arr[i]=='<'){
//                if(size>0){
//                    size--;
//                }
//            }
//            else{
//                str[size++]=arr[i];
//            }
//        }
//        String c=new String(str);
//        return c.substring(0,size);
//    }
//}









//最大数
//import java.util.*;
//
//
//public class Solution {
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     *
//     * @param s string字符串
//     * @return int整型
//     */
//    public int solve (String s) {
//        // write code here
//        char[] arr=s.toCharArray();
//        int max=Integer.MIN_VALUE;
//        int res=0;
//        for(char c : arr ){
//            if(c>='0'&&c<='9'){
//                res=res*16+c-'0';
//            }else if(c>='A'&&c<='F'){
//                res=res*16+c-'A'+10;
//            }else{
//                max=max>res?max:res;
//                res=0;
//            }
//        }
//        return max;
//    }
//}










//判断回文
//import java.util.*;
//
//
//public class Solution {
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     * @param str string字符串 待判断的字符串
//     * @return bool布尔型
//     */
//    public boolean judge (String str) {
//        // write code here
//        char[] arr=str.toCharArray();
//        int end=str.length()-1;
//        int begin=0;
//        while(begin<end){
//            if(arr[begin]!=arr[end]){
//                return false;
//            }
//            begin++;
//            end--;
//        }
//        return true;
//    }
//}












//括号序列
//import java.util.*;
//
//
//public class Solution {
//    /**
//     *
//     * @param s string字符串
//     * @return bool布尔型
//     */
//    public boolean isValid (String s) {
//        // write code here
//        int len=s.length();
//        char[] arr=new char[len];
//        int size=0;
//        for(int i=0;i<len;i++){
//            char tmp=s.charAt(i);
//            if(isLeft(tmp)){
//                arr[size++]=tmp;
//            }
//            else{
//                if(size<=0){
//                    return false;
//                }
//                if(paif(arr[size-1],tmp)){
//                    size--;
//                }
//                else{
//                    return false;
//                }
//            }
//        }
//        return size==0;
//    }
//    public static boolean isLeft(char left){
//        return left=='{'||left=='['||left=='(';
//    }
//    public static boolean paif(char left,char right){
//        return (left=='{'&&right=='}')
//                ||(left=='['&&right==']')
//                ||(left=='('&&right==')');
//    }
//}









//反转字符串
//import java.util.*;
//
//
//public class Solution {
//    /**
//     * 反转字符串
//     * @param str string字符串
//     * @return string字符串
//     */
//    public String solve (String str) {
//        // write code here
//        char[] value=str.toCharArray();
//        int end=str.length()-1;
//        int begin=0;
//        while(begin<=end){
//            char tmp=value[begin];
//            value[begin]=value[end];
//            value[end]=tmp;
//            begin++;
//            end--;
//        }
//        return String.copyValueOf(value);
//    }
//}




//反转字符串
//    public static String fun(String str,int begin,int end){
//        char[] value=str.toCharArray();
//        while(begin<=end){
//            char tmp=value[begin];
//            value[begin]=value[end];
//            value[end]=tmp;
//            begin++;
//            end--;
//        }
//
//        return String.copyValueOf(value);
//    }
//    public static void main(String[] args){
//        Scanner scan=new Scanner(System.in);
//        while(scan.hasNext()){
//            String str=scan.nextLine();
//            String ret=fun(str,0,str.length());
//            System.out.println(ret);
//        }
//    }










//字符串连接
//import java.util.Scanner;
//public class Main{
//    public static String fun(String str){
//        String[] ret=str.split(" ");
//        String str2="";
//        for(String s:ret){
//            str2+=s;
//        }
//        return str2;
//    }
//    public static void main(String[]args){
//        Scanner scan=new Scanner(System.in);
//        String str=scan.nextLine();
//        String ret=fun(str);
//        System.out.println(ret);
//    }
//}
